
//preloading.....
load("library/common.js");

JEuler.system.loadJS("library/math.js");

(function() {

    //JEuler.system.loadJS("data/???.dat");
    JEuler.system.printCaption("237");
    JEuler.system.startTimerCount();

    var BASE = Math.pow(10,8)
    var TEN_12 = Math.pow(10,12);
    var TEN_10 = Math.pow(10,10);
    var TEN_6 = Math.pow(10,6);
    var TEN_4 = 10000;
    var A=[2, 2, -2, 1], B=[2, 2, -2, 1]
    
    //We have formula T[n]=2*T[n-1]+2*T[n-2]-2*T[n-3]+T[n-4] and T[1-4] = [1, 1, 4, 8]
    
    var getNextB = function(A, B) {
        var nextB=[B[0]*A[0]+B[1], B[0]*A[1]+B[2], B[0]*A[2]+B[3], B[0]*A[3]]
        for(var i=0; i<4; i++) {
            nextB[i] = nextB[i]%BASE;
            if(nextB[i]<0) nextB[i] = nextB[i] + BASE;
        }
        return nextB;
    }
    
    var getNextX = function(X, A) {
        var nextX=0, t1, t2, t3, t4;
        for(var i=0; i<4; i++) {
            if(Math.abs(X[3-i])>TEN_4 && Math.abs(A[i])>TEN_4){
                //Javascript don't support 10^16 precision, so ....
                t1 = X[3-i]%TEN_4; t2 = X[3-i]-t1;
                t3 = A[i]%TEN_4;   t4 = A[i] - t3;
                nextX += (t1*t3) + (t2*t3) + (t1*t4);
            } else {
                nextX += (X[3-i]*A[i])%BASE
            }
        }
        nextX = nextX%BASE;
        if(nextX<0) nextX = nextX + BASE;        
        return nextX;
    };
        
    var B1=B, B2, BB=[null];
    BB.push(A);
    for(var i=1; i<=TEN_6+1; i++) {
        B1=getNextB(A, B1);
        BB.push(B1);
    }
    
    var X = [1,1,4,8]
    
    var calculate = function(iStart, iStep, iLast) {
        
        var X1=X, X2=[], tmp;//, iStart=4, iStep=5, iLast=100;
        while(iStart<iLast) {
            X2 = [];
            X2[0] = getNextX(X1, BB[iStep-3]); // 1 + TEN6;
            X2[1] = getNextX(X1, BB[iStep-2]); // 2 + TEN6;
            X2[2] = getNextX(X1, BB[iStep-1]); // 3 + TEN6;
            X2[3] = getNextX(X1, BB[iStep-0]); // 4 + TEN6;
            //print(iStart + ":" + X2);
            iStart = iStep+iStart;
            //print(iStart);
            
            if(iStart + iStep > iLast) {
                if(iStart == iLast) {
                    JEuler.system.print("T[10^12]="+X2[3]);
                } else {
                    JEuler.system.print("T[10^12]="+getNextX(X2, BB[iLast-iStart]));
                }
                break;
            }
            X1 = X2;
        }
    };
    
    calculate(4, TEN_6, TEN_12);
    JEuler.system.printTimerCount();
    
})();
